package ds.heap;



/**
 * 堆
 * 
 * ①.堆是【完全二叉树】。即，除了树的最后一层节点不需要是满的，其他的每一层从左到右完全是满的
 * ②.常常用一个数组实现，结合①可知，这个数组中”没有洞“
 * ③.组织规则：堆中的每一个节点的关键字都大于（或等于）这个节点的子节点的关键字
 * 
 */
public class Heap {

	private Node[] nodeArray;
	private int maxSize;
	private int currentSize;
	// ---------------------------
	public Heap(int maxSize) {
		this.maxSize = maxSize;
		currentSize = 0;
		nodeArray = new Node[maxSize];
	}
	
	public boolean isEmpty()
	{
		return currentSize == 0;
	}
	
	public boolean insert(int key)
	{
		if(currentSize == maxSize)
		{
			return false;
		}
		
		Node newNode = new Node(key);
		nodeArray[currentSize] = newNode;
		trickleUp(currentSize++);
		return true;
	}
	
	// 向上筛选
	private void trickleUp(int index)
	{
		int parent = (index - 1) / 2;
		Node bottom = nodeArray[index];
		while(index > 0 && nodeArray[parent].getKey() < bottom.getKey())
		{
			nodeArray[index] = nodeArray[parent];
			index = parent;
			parent = (parent-1) / 2;
		}
		nodeArray[index] = bottom;
	}
	
	public Node remove()
	{
		Node root = nodeArray[0];
		nodeArray[0] = nodeArray[--currentSize];
		trickleDown(0);
		return root;
	}

	// 向下筛选
	private void trickleDown(int index)
	{
		int largerChild;
		Node top = nodeArray[index];
		while(index < currentSize / 2) // 到最底层时结束
		{
			int leftChild = 2*index + 1;
			int rightChild = leftChild + 1; 
			
			// find larger child
			if(rightChild < currentSize && // rightChild exists?
			   nodeArray[leftChild].getKey() < nodeArray[rightChild].getKey())
			{
				largerChild = rightChild;
			}
			else
			{
				largerChild = leftChild;
			}
			
			if(top.getKey() >= nodeArray[largerChild].getKey())
				break;
			
			nodeArray[index] = nodeArray[largerChild];
			index = largerChild; // 嗯嗯
		} // end while
		nodeArray[index] = top;
	}
	
	public boolean change(int index, int newValue)
	{
		if(index<0 || index >= currentSize)
			return false;
		int oldValue = nodeArray[index].getKey(); // remember old
		nodeArray[index].setKey(newValue); // change to new
		
		if(oldValue < newValue)
			trickleUp(index);
		else
			trickleDown(index);
		return true;
	}
	
	public void displayHeap() {
		// TODO
	}
}